1. Field of the Invention
The present invention relates generally to computer-implemented image registration, and more specifically to the image registration wherein the positional relationships between the images are correctly and rapidly determined in order to precisely merge the images into a single synthesized one.
2. Description of the Related Art
Pictures are typically acquired into a computer system using CCD (charge coupled device) cameras, scanners, etc. However, if a picture is too wide to take the entire picture at a time, due to a limited view angle of the camera (for example), it is necessary to separately take a plurality of partial pictures. Thereafter, the partial pictures are acquired into the computer wherein the picture images are merged into a single synthesized image. In order to automatically merge the partial images using a computer system, a variety of image registration techniques have been proposed.
The known registration techniques typically determine the parameters for image matching, using indexes such as residuals or cross-correlation coefficients, by way of sequential search within a parameter space formed by all parameter candidates. Some examples of such techniques are disclosed in a pager entitled xe2x80x9cA Survey of Image Registration Techniquesxe2x80x9d by Lisa G. Brown, ACM Computing Surveys, Vol. 24, No. 4, December 1992 (Related Art 1). However, this related art suffers from the drawbacks that the number of calculations exponentially increases with increase in the number of parameters included.
One known approach to reducing the number of calculations is disclosed in Japanese Laid-open Patent Application No. 7-264483 (Related Art 2) wherein techniques for matching X-ray images are described. According to this related art, a feature point is extracted from the image, after which the image portion in close vicinity of the feature point is divided into blocks. Subsequently, each block is processed to determine only the amount of parallel movement (viz., block matching). The results thus obtained are combined using least squares method, after which various parameters are determined which are related to the amount of parallel movement, rotation, magnification, and reduction. According to this related art, the parameter space is formed only by the amount of parallel movement and thus, it is able to prevent the exponential increase in the number of calculations.
Further, Japanese Laid-open Patent Application No. B-145628 (Related Art 3) discloses another technique wherein block matching is applied to a plurality of templates. The matching results are used to determine the parameters indicating the amount of parallel movement rotation, etc. in connection each of the all combinations of blocks. Lastly, the parameter that exhibits the minimum square error is determined as the result of the image registration.
However, according to the conventional registration using the blocking matching, such as disclosed in Related Art 2, the parameter space is composed only of the amount of parallel movements and thus, the exponential increase in the number of calculations is able to be prevented. However, such a known technique has encountered the difficulty that the parameters obtained are liable to be adversely affected by the blocks that provide the incorrect amount of parallel movement, and accordingly, the parameters are no longer determined precisely.
On the other hand, Related Art 3 is able to solve the above-mentioned problem inherent in Related Art 2 by way of selecting the parameters, which minimize the square error, among the parameters ascertained with every block combination. However, according to Related Art 3, the parameters which are deemed appropriate are determined solely on the basis of the block matching results. Accordingly, if some of the blocks causes identical or similar errors in determining the amount of parallel movement, the known technique disclosed in Related Art 3 is no longer expected to provide reliable results.
It is therefore an object of the present invention to eliminate the problems inherent in the above-mentioned conventional image registration.
Another object of the present invention is to provide the image registration techniques wherein the positional relationships between images are precisely and rapidly determined in order to correctly merge the images into a single synthesized one.
In brief, these objects are achieved by the techniques wherein in order to perform image registration of first and second images using block matching wherein the first image is divided into a plurality of blocks, the plurality of blocks are classified into a plurality of block groups, using block matching results, such that the blocks classified into the same block group are considered to produce similar position correcting parameters. A plurality of position correcting parameters is determined with each of the plurality of block groups specified above. Thereafter, most appropriate position correcting parameters are determined, among the position correction parameters determined by referring to the first and second images.
One aspect of the present invention resides in an apparatus for performing computer implemented image registration of first and second images using block matching wherein the first image is divided into a plurality of blocks, comprising: first means for classifying the plurality of blocks into a plurality of block groups, using block matching results, such that the blocks classified into the same block group are considered to produce similar position correcting parameters; second means for determining a plurality of position correcting parameters with each of the plurality of block groups determined by the first means; and third means for determining most appropriate position correcting parameters, among the plurality of position correction parameters determined by the second means, by referring to the first and second images.
Another aspect of the present invention resides in an apparatus for an apparatus for determining positional relationship between first and second images in order to implement registration of the first and second images, comprising: a first memory;
a block divider for dividing the first image into a plurality of blocks and determining attribute data of each block which is stored in the first memory; a block selector for determining block characteristic values of each block by referring to the first image and the attribute data stored in the first memory, the block selector selecting, using the block characteristic values, a plurality of blocks each of which is considered that there is little possibility of causing an erroneous result when the block matching is implemented on the block; block matching means for implementing block matching on the blocks selected by the block selector and determining corresponding points of the first and second images, the corresponding points being stored in the first memory; a block classifier for classifying the plurality of blocks into a plurality of block groups, using block matching results, such that the blocks classified into the same block group are considered to produce similar position correcting parameters; a second memory; means for determining position correcting parameters for each of a plurality of block groups, the position correcting parameters being stord in the second memory; and a parameter determiner for determining a position correcting parameter, among the plurality of position correction parameters, determined by the means, for most appropriately matching the first and second images.
Still another aspect of the present invention resides in a method of performing computer-implemented image registration of first and second images using block matching wherein the first image is divided into a plurality of blocks, comprising the steps of: (a) classifying the plurality of blocks into a plurality of block groups, using block matching results, such that the blocks classified into the same block group are considered to produce similar position correcting parameters; (b) determining a plurality of position correcting parameters with each of the plurality of block groups determined by the first means; and (c) determining most appropriate position correcting parameters, among the plurality of position correction parameters determined by the second means, by referring to the first and second images.
Still another aspect of the present invention resides in a method of determining positional relationship between first and second images in order to register the first and second images, comprising the steps of: (a) dividing the first image into a plurality of blocks and determining attribute data of each block which is stored in a first memory; (b) determining block characteristic values of each block by referring to the first image and the attribute data stored in the first memory, and selecting, using the block characteristic values, a plurality of blocks each of which is considered that there is little possibility of causing an erroneous result when the block matching is implemented on the block; (c) implementing block matching on the blocks selected at step (b) and determining corresponding points of the first and second images, the corresponding points being stored in the first memory; (d) classifying the plurality of blocks into a plurality of block groups, using block matching results, such that the blocks classified into the same block group are considered to produce similar position correcting parameters; (e) determining position correcting parameters for each of a plurality of block groups, the position correcting parameters being stored in a second memory; and (f) determining a position correcting parameter, among the plurality of position correction parameters stored in the second memory, for most appropriately matching the first and second image.